home *** CD-ROM | disk | FTP | other *** search
/ Aminet 22 / Aminet 22 (1997)(GTI - Schatztruhe)[!][Dec 1997].iso / Aminet / game / think / WhiteLion.lha / WhiteLion / WhiteLion.doc < prev    next >
Text File  |  1997-09-15  |  14KB  |  257 lines
  1. -----------------------------------------------------------------------------
  2. ---- WhiteLion 1.31 (07. Sept. 1997) ----------------------------------------
  3. -----------------------------------------------------------------------------
  4. ---- Program Documentation --------------------------------------------------
  5. -----------------------------------------------------------------------------
  6.  
  7. -----------------------------------------------------------------------------
  8. ---- getting started --------------------------------------------------------
  9. -----------------------------------------------------------------------------
  10.  
  11. To play, just doubleclick on the WhiteLion icon, and on the [?] gadget in the
  12. program window. It should work fine on all Amigas with Kickstart 1.2 or
  13. higher. Try a game and don't be disappointed if you lose. You'll soon get
  14. used to it...
  15. On Hires Laced Screens, you need the Topaz 11 Font.
  16. Just in case you haven't installed it on your HD yet, insert your Workbench
  17. Fonts disk into DF0:, open a Shell and type:
  18.   Copy DF0:Fonts/Topaz#? SYS:Fonts ALL
  19.  
  20. -----------------------------------------------------------------------------
  21. ---- for german-only speaking users                 -------------------------
  22. ---- (there might still be some, you never know...) -------------------------
  23. -----------------------------------------------------------------------------
  24.  
  25. Zum Start klicken Sie bitte zweimal schnell auf das WhiteLion Icon. Setzen
  26. können sie einfach durch Mausklick auf das gewünschte Feld. Die deutsch-
  27. sprachige Version habe ich vorerst nicht fortgesetzt, da es doch eine
  28. Menge Arbeit ist, alles nochmal auf Deutsch zu übersetzen. Wenn genug Inter-
  29. esse besteht, kann ich aber 'Localization', d.h. hier Vielsprachigkeit, zu
  30. einem späteren Zeitpunkt implementieren.
  31. Sie benötigen den Topaz 11 Font, um auf Hires InterLaced Screens zu spielen.
  32. Legen Sie ggf. die Workbench Fonts Diskette in DF0:, starten Sie die Shell
  33. und geben Sie ein:
  34.   Copy DF0:Fonts/Topaz#? SYS:Fonts ALL
  35. Wenn Sie wirklich kein Englisch können, try and error :^>>
  36.  
  37. -----------------------------------------------------------------------------
  38. ---- background information -------------------------------------------------
  39. -----------------------------------------------------------------------------
  40.  
  41. Always being fascinated by artificial intelligence, I started to write this
  42. program in 1991, when I still worked in an old people's home in Hanover.
  43. In Germany you have to fulfil a social civil service if you don't go to the
  44. german army.
  45. My first idea was to use a very quick, move-oriented evaluation of the game
  46. positions to let the program calculate many moves ahead. But the result was
  47. a quite weak, silly playing game which looked four or five moves ahead,
  48. evaluated the resulting positions wrong and tried to reach one of the wrong-
  49. valued new positions.
  50.  
  51. So I implemented the standard AI alpha-beta pruning algorithm and a position-
  52. oriented evaluation after a while.
  53. In 1992 I found a very useful article by Paul S. Rosenbloom in the Paderborn
  54. University library called 'IAGO - A World Championship Level Othello
  55. Program', published in 'Artificial Intelligence, vol. 19 (1982)'.
  56. This is where I got most of the Minimum Disk Strategy and the Mobility
  57. measurement inspirations from. I then decided to write my own functions for
  58. the border and inner-room evaluation.
  59. The idea of AI games is the following:
  60. Let's assume the computer has to move and there are 12 possible moves in this
  61. position. It executes the possible moves internally, i.e. builds up all 12
  62. new board positions, and saves them. Then it calls an evalutation function
  63. for all saved boards, and the one which gets the highest number is chosen.
  64. If you want the computer to think ahead, let it compute the 12 following
  65. boards ('sons') first, and then for each of the 12 sons compute all following
  66. boards ('grandsons') again. Then evaluate the grandsons, and choose that one
  67. of your sons for play which gives you the best value if the human finds the
  68. best grandson afterwards.
  69. For three moves ahead, compute all grandgrandsons...
  70. This method is called MINIMAX.
  71. In fact, you needn't compute all of them. There is a heuristic search
  72. algorithm called 'alpha-beta pruning' which will give you exactly the same
  73. (MINIMAX) result, but will create less boards:
  74. If the average number of moves per board position is called 'b', and the
  75. search depth 'd', it will only use ca. 2*b^[d/2] instead of b^d moves.
  76.  
  77. The FD version provides different strategies on the 3 available levels:
  78. Level 1 uses the Max Disk count strategy, adds a border evaluation and
  79. changes the count evaluation as the game proceeds. The search depth is 1.
  80. Level 2 also uses border, count, and in the opening an additional
  81. 'inner room' evaluation is used to prevent the opponent from getting to the
  82. border too early. It also (mainly) adds a mobility measure evaluation which
  83. counts the moves you have got, the moves the computer would be able to make
  84. and the moves both of you have. It then returns a number which shows the
  85. mobility difference of the players. The search depth is 2.
  86. Level 3 uses the same evaluation as Level 2, but the search depth is 3
  87. halfmoves ahead now. This should be strong enough already to let you guess at
  88. the strength of the registered version.
  89. See the [?] help window explanations for more.
  90.  
  91. You'll see that the evaluation function, not the search depth, is essential
  92. for the strength. If the machine looks eight moves ahead, but evaluates the
  93. occuring boards wrong, it will try to get to a wrong position. If it gets
  94. good values near to the real ones, one (halve-)move ahead will be strong
  95. already. If you take a greater search depth then, the game will soon become
  96. unbeatable. But note, in general a computer will never play perfect if it
  97. does not search up to the very end. If you've got only endboards to evaluate,
  98. you've just got to detect who has won. You may then force a win by simply
  99. moving to a position wherefrom all endboards are victories, if it is at all
  100. possible. Currently WhiteLion searches for endgame positions from move
  101. (55-LevelNr/2) on, (56-LevelNr) in the registered version.
  102.  
  103. If you like the game so far, please consider sending me the Shareware fee.
  104. Then you'll receive the source code with more explanations on the algorithms
  105. and the executable programs. The source is in C and has been compiled with
  106. DICE, a freely distributable C compiler from Fish Disk 491. I also tried Manx
  107. Aztec C 5.0a, but DICE was both faster and created the smaller executable.
  108. Thanks, Matt! (And I'm a registered user now :)
  109.  
  110. You'll also receive the registered version of WhiteLion 1.3. You'll note the
  111. new Settings menu with various options explained in the program's [?] window.
  112. And WhiteLion now plays a very strong and mysterious strategy, which is
  113. called the Minimum Disk Strategy. The idea is, WhiteLion tries to get as few
  114. disks as possible in the opening game, to reduce the number of moves you may
  115. choose from. You'll find that if you've got less moves, the bad ones are
  116. still there, while the good ones seem to have disappeared. While the game
  117. continues, WhiteLion gets into a strong position and catches all disks back
  118. in the endgame. You'll see! Here the level number is equal to the number of
  119. halvmoves WhiteLion calculates ahead.
  120.  
  121. The Shareware fee is 10 DM, 7 US$ or 4 british £ in banknotes. I presume it
  122. is not too much if you consider how much time I invested to write the game.
  123. (roughly estimation: at least 1500 hours, wherefrom 1000 hours were used up
  124. by the search and evaluation move programming).
  125. Wrap your bills into a paper sheet to protect them from curious eyes on their
  126. journey, and simply send them in a standard envelope letter, asking for the
  127. registered version of WhiteLion.
  128. As I found out one can get 100 of those goodlooking new 5 DM bills right from
  129. the Bundesbank (with serial numbers from ...00 to ...99) when asking for at
  130. a Sparkasse, I wouldn't ask for you sending them any longer...
  131. I'd be interested in your basic computer model and your Kickstart/Workbench
  132. version. If you've got any suggestions on how to strengthen the evaluation or
  133. want a user interface feature or if you found a bug (i.e. weird behaviour),
  134. I'd be glad to hear from you. But if you don't want to, you needn't write a
  135. whole letter. I promise I'll send back the disk as soon as possible, in
  136. general the next working day. If you've got an EMail address, I can also send
  137. you the game over the wire, packed with lha and uuencoded (please ask if you
  138. wouldn't know how to extract the files). This will usually be even faster and
  139. saves me the expenses for disk and stamps. Just let me know. When I receive
  140. the first letter from Japan, I'll be glad to send back the money. I know that
  141. Othello is very popular there (next to Go, of course...), and I'd especially
  142. like any measurement on WhiteLion's strength from there.
  143. To express my gratefulness, all users who have sent their fee so far get the
  144. registered 1.3 version for free.
  145.  
  146. I'll keep the right to develop a major new version of Othello even if I get
  147. less then 20 registrations, but it is quite unlikely. I don't want to write
  148. complex programs if noone is interested in them afterwards.
  149.  
  150. Plans for WhiteLion 2.0 include:
  151.  
  152. - complete new user interface according to the Style Guide, including Menus,
  153.   MenuHelp, 2D/3D board display, OS 2 style cycle and slider gadgets, and
  154.   special OS 3 features like 256 colour display and localization. As a result,
  155.   this major new version will require OS 2.04 as a minimum platform to run.
  156.   I'm definitely not going through this 'have to keep it 1.2 compatible'
  157.   problems again. I might consider putting the stronger algorithms described
  158.   below into the OS 1.2 version, if there is enough interest. I might also
  159.   give away a licence and the necessary sources instead if someone asks.
  160.   The new WhiteLion1.3 Settings requester is a typical example how I presume
  161.   to design this new version.
  162.  
  163. - ARexx and Library implementation so you may try out your own strategy by
  164.   remixing and weighting the evaluation components. You will be able to
  165.   easily simulate the whole search process using the library calls so you'll
  166.   need ARexx only to supply the result. This ensures it will still be fast.
  167.  
  168. - replacement of the a-ß algorithm with the faster SSS*; replacement of SSS*
  169.   with SCOUT in the endgame, when the number of possible moves gets lower;
  170.   replacement of SCOUT with SOLVE when the computer begins to search to the
  171.   very end.
  172.  
  173. - tournament mode to play against clocks. Implementation of time-dependant
  174.   search depth and time usage strategy.
  175.  
  176. - rewriting of the mobility evaluation. Spreading of the mobility evaluation
  177.   over the search tree to save time, i.e. counting the moves while building
  178.   up the tree.
  179.  
  180. - your suggestions. Just tell me.
  181.  
  182. -----------------------------------------------------------------------------
  183. ---- legal stuff ------------------------------------------------------------
  184. -----------------------------------------------------------------------------
  185.  
  186. In the following context, 'This Program' means the whole WhiteLion1.3 package
  187. as described below. If any part of the following context should be illegal
  188. under a country's law, the whole rest remains valid nevertheless.
  189.  
  190. This Program is © (c) MXMII, MXMIII by me, Martin Grote, born 25.04.1970.
  191. All Rights Reserved Worldwide.
  192.  
  193. This Program must not be changed by anyone except written permission by me or
  194. for personal use only.
  195.  
  196. This Program is Shareware. Only the special FD version may be freely
  197. redistributed. It may be distributed only as the whole package, a directory
  198. containing the following files:
  199.  
  200.   WhiteLion
  201.   WhiteLion.info
  202.   WhiteLion.doc
  203.   WhiteLion.doc.info
  204.   README
  205.   README.info
  206.  
  207. The whole package may be packed with a program like 'lha', and be redistri-
  208. buted as such, if no extra charge is applied for this. It must unpack to
  209. This Program then.
  210.  
  211. I would be glad if Mr. Fred Fish, Amiga Library Disks, would consider placing
  212. This Program on one of his AmigaLibDisks. He may distribute it for whatever
  213. he assumes necessary then.
  214. In no case may anyone else redistribute This Program for more than 5 US$,
  215. five US dollars, without written permission from the author.
  216. In Germany This Program must not be distributed for more than 5 DM; in our
  217. words:
  218.  
  219. »»»» Dieses Programm darf in Deutschland nicht für mehr als 5 (fünf) DM  ««««
  220. »»»» vertrieben werden, falls keine schriftliche Erlaubnis von mir       ««««
  221. »»»» vorliegt.                                                           ««««
  222. »»»»                 Dies gilt auch für Warenhausketten!                 ««««
  223.  
  224. This Program or any part of it may not be included into a commercial program
  225. package without written permission from the author. Just ask me.
  226.  
  227. No warranty is given that This Program serves for any special purpose.
  228. Use it on your own risk. No damage is intended, but the author can not be
  229. made reliable for any damage caused by This Program nevertheless.
  230.  
  231. -----------------------------------------------------------------------------
  232.  
  233. Nordborchen, 20th of January,   1993. (V1.2)
  234. Nordborchen, 22nd of August,    1993. (V1.3)
  235. Paderborn,   7th of September,  1997. (V1.31)
  236.  
  237. I HAVE MOVED to Paderborn!
  238. The address shown by the program is no longer valid!
  239.  
  240. Here's my new address:
  241. -----------------------------------------------------------------------------
  242.  
  243. Martin Grote
  244. Bernhard-Koethenbuerger-Str. 91
  245. 33102 Paderborn
  246. Germany, EC
  247.  
  248. EMail: chandler@uni-paderborn.de, chandler@c-lab.de
  249.  
  250. -----------------------------------------------------------------------------
  251.  
  252. VISIT MY NEW WEBSITE
  253.  
  254.   at  www.c-lab.de/~chandler
  255.  
  256. and take part in the famous WhiteLion user query!
  257.